def fib_dp(n):
    if n <= 1:
        return n
    
    # 创建DP表，存储中间结果
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    
    # 自底向上计算
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# 空间优化版本（只保存前两个值）
def fib_optimized(n):
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1  # F(0), F(1)
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

# 测试
print("\n动态规划方法：")
for i in range(10):
    print(f"F({i}) = {fib_dp(i)}")

print(f"\nF(40) = {fib_optimized(40)}")  # 快速计算出结果